package com.qjc.demo.train.dp;

/**
 * @ClassName: Fiber3
 * @Description: 斐波那契数列：DP方程（动态规划）
 * 时间复杂度为O(n)
 * 优点：时间复杂度和空间复杂度都相当较低
 * 缺点：难，有些场景不适用
 * @Author: qjc
 * @Date: 2022/5/4 2:18 PM
 */
public class Fiber3 {

    public static long fib(int n) {
        long[] a = new long[n + 1];
        a[0] = 0;
        a[1] = 1;
        for (int i = 2; i <= n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        return a[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(64));
    }

}
